#include <sys/mman.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>


/* hold a list of memory segments alloced by us */
void* memHead = NULL;

int MEM_SEGMENT_SIZE = 100000;

int MEM_SEGMENT_HEADER_SIZE = 2*sizeof(void*)+sizeof(int);
int SIZE = sizeof(void*);
int NEXT = sizeof(void*)+sizeof(int);

int SEGMENT_HEADER_SIZE = 2*sizeof(void*)+sizeof(int)+sizeof(char);
int FREE = sizeof(int);
int NEXT_FREE = sizeof(int)+sizeof(char);
int PREV_FREE = sizeof(int)+sizeof(char)+sizeof(void*);

int SEGMENT_FOOTER_SIZE = sizeof(int);


/* fills a segment header and footer with the given parameters */
void fillHeader(void *add, int size, char free, void *prev, void *next) {
	/* fill the segment's size */
	memcpy (add, &(size), sizeof(int));
	/* fill if the segment is free - yes(1) or no(0) */
	memcpy (add + FREE, &(free), sizeof(char));
	/* fill the prev_free and next_free - not relevent for an allocated segment (NULL in that case) */
	memcpy (add + NEXT_FREE, &(next), sizeof(void*));
	memcpy (add + PREV_FREE, &(prev), sizeof(void*));
	/* fill the footer of the segment */
	memcpy (add + SEGMENT_HEADER_SIZE + size, &(size), sizeof(int));
}

/* updates the header from free to aloocated */
void allocate(void * add) {
	memcpy (add + FREE, &(free), sizeof(char));
}

/* fills a mem segment header with the given parameters */
void fillMemHeader(void *add, int size, void *free) {
	void *null = NULL; 
	/* fill the pointer the first free block (the smallest) - only used when this is the first mem segment */
	memcpy (add, &(free), sizeof(void*));
	/* fill the size of the segment - used to free it */
	memcpy (memHead + SIZE, &(size), sizeof(int));
	/* fill the pointer to the next memory segment - always NULL at first */
	memcpy (memHead + NEXT, &(null), sizeof(void*));
}

/* updates the header of the given mem segment with a pointer to the nest segment */
void updateNextMem(void *add, void *next) {
	memcpy (add + NEXT, &(next), sizeof(void*));
}

/* creates a new memory segment, initializes it, allocates inside it the number of butes specified and returns it's address */
void* createMemSegment (size_t size) {
	void *add;
	char one = 1, zero = 0;
	void *null = NULL;
	int freeSize, second;
	size_t secondSize;
	
	if (size > (size_t) MEM_SEGMENT_SIZE) {
		/* special case for a single very big allocation - there's no second segment */
		secondSize = size + MEM_SEGMENT_HEADER_SIZE + SEGMENT_HEADER_SIZE + SEGMENT_FOOTER_SIZE;
		add = mmap(NULL, secondSize, );
		if (add == NULL) return NULL;

		/* fill the header of the memory segment */
		/* there is no free segment - only one segment which is full */
		fillMemHeader(memHead, secondSize, NULL);
	} 
	else {
		/* fill the header of the second free segment inside it - all the rest */
		second = MEM_SEGMENT_HEADER_SIZE + SEGMENT_HEADER_SIZE + size + SEGMENT_FOOTER_SIZE;
		secondSize = MEM_SEGMENT_SIZE - MEM_SEGMENT_HEADER_SIZE - size - 2*SEGMENT_HEADER_SIZE - 2*SEGMENT_FOOTER_SIZE;
		fillHeader(memHead + second, secondSize, (char) 1, NULL, NULL);

		/* fill the header of the memory segment */
		/* first free address is the addrss of the second segment */
		fillMemHeader(memHead, MEM_SEGMENT_SIZE, memHead + second);
	}	
	/* fill the header of the first segment inside it - allocate */
	fillHeader(memHead + MEM_SEGMENT_HEADER_SIZE, size, (char) 0, NULL, NULL);
	return add;
}

/* remove from the free list */
void removeFree(void *add) {
	void *prev, *next;
	memcpy(&(prev), add + PREV_FREE, sizeof(void*)); 
	memcpy(&(next), add + NEXT_FREE, sizeof(void*)); 
	if (prev != NULL) memcpy(prev + NEXT_FREE, &(next), sizeof(void*));
	if (next != NULL) memcpy(next + PREV_FREE, &(prev), sizeof(void*));
}

void createFree(void *add, int size) {
	void *curr, *next, *null = NULL;
	int nextSize, currSize;
	fillHeader(add, size, 1, NULL, NULL);
	
	/* insert to the free list, at the right place accordind to the size */
	/* get a ptr to the address of the first and second free spaces (the smallest) */
	memcpy(&(curr), memHead, sizeof(void*)); /* ??? */
	if (curr == NULL) {
		/* the free list is empty */
		memcpy(add + NEXT_FREE, &(null), sizeof(void*));
		memcpy(add + PREV_FREE, &(null), sizeof(void*));
		memcpy(memHead, &(add), sizeof(void*));
	} 
	else {
		memcpy(&(currSize), curr, sizeof(int));
		if (currSize >= size) {
			/* this block should be the head of the free list */
			memcpy(add + NEXT_FREE, &(curr), sizeof(void*));
			memcpy(add + PREV_FREE, &(null), sizeof(void*));
			memcpy(curr + PREV_FREE, &(add), sizeof(void*));
		} 
		else {
			memcpy(&(next), curr + NEXT_FREE, sizeof(void*));
			/* move on the list untill next >= size */
			while (next != NULL) {
				memcpy(&(nextSize), next, sizeof(int));
				if (nextSize >= size) break;
				/* incr the pointers */
				curr = next;
				memcpy(&(next), next + NEXT_FREE, sizeof(void*)); /* ??? */  
			}
			memcpy(add + NEXT_FREE, &(next), sizeof(void*));
			memcpy(add + PREV_FREE, &(curr), sizeof(void*));
			memcpy(curr + NEXT_FREE, &(add), sizeof(void*));
			memcpy(next + PREV_FREE, &(add), sizeof(void*));
		}
	}
}

/* receives a free block address, allocates the needed space inside it and updates the free blocks list */
void allocateAndUpdate(void *add, int size, int blockSize) {
	int restSize;
	removeFree(add);
	
	restSize = blockSize - size - 2*SEGMENT_HEADER_SIZE -2*SEGMENT_FOOTER_SIZE;
	if (restSize > 0) {  
		/* create a new free block from the rest and add it to the free list */
		createFree(add + SEGMENT_HEADER_SIZE + SEGMENT_FOOTER_SIZE, restSize);
		/* update the header */
		fillHeader(add, size, 0, NULL, NULL);
	}
	else 
		/* there's no room to split it into 2 blocks, so it stays as 1 block in the same size as before */
		allocate(add);
}

/* finds and allocates a free segment (at the smallest size possible that is larger then size) and returns it's address */
void* findFreeSpace (size_t size) {
	void *add, *memTmp, *memNext;
	int blockSize;

	/* get a ptr to the address of the first free space (the smallest) */
	memcpy(&(add), memHead, sizeof(void*)); /* ??? */
	/* find the smallest free block that is big eanough for the allocation */
	while (add != NULL) {
		memcpy(&(blockSize), add, sizeof(int));
		if ((size_t) blockSize >= size) break;
		/* move to the next free space */
		memcpy(&(add), add + NEXT_FREE, sizeof(void*)); /* ??? */  
	}
	if (add == NULL) { 
		/* there is no free block - allocate a new mem segment */
		add = createMemSegment(size);
		/* reach the end of the mem segments list */
		memTmp = memHead;
		memcpy(&(memNext), memTmp + NEXT, sizeof(void*)); /* ??? */
		while (memNext != NULL) {
			memTmp = memNext;
			memcpy(&(memNext), memTmp + NEXT, sizeof(void*)); /* ??? */  
		}
		/* link the last mem segment to the new one */
		updateNextMem(memNext, add);
		return add + SEGMENT_HEADER_SIZE + SEGMENT_HEADER_SIZE;
	}
	/* we found a free block that's big enough */
	allocateAndUpdate(add, size, blockSize);
	return add + SEGMENT_HEADER_SIZE;
}

void* myMalloc (size_t size) {
	if (memHead == NULL) {
		memHead = createMemSegment(size);
		if (memHead == NULL) fprintf(stderr, "Error: mmap failed"); /* ??? */
		return memHead + MEM_SEGMENT_HEADER_SIZE + SEGMENT_HEADER_SIZE;
	}
	return findFreeSpace(size);
}

/* connects a free space with it's free neighbors */
void mergeFree(void *add, int size, void *prev, int prevSize, void *next) {
	int newSize = size, nextSize;
	void *prevAdd, *nextAdd;
	if (prev != NULL) {
		newSize += prevSize;
		removeFree(prev);
		if (next != NULL) {
			memcpy(&(nextSize), next + SIZE, sizeof(int));
			newSize += nextSize;
			removeFree(next);
		}
		createFree(prev, newSize);
	} 
	else {
		if (next != NULL) {
			memcpy(&(nextSize), next + SIZE, sizeof(int));
			newSize += nextSize;
			removeFree(next);
		}
		createFree(add, newSize);
	}
}

void myFree (void* add) {
	char prev, next;
	int size, prevSize;
	memcpy(&(size), add, sizeof(int));
	/* check for free neighbors */
	memcpy(&(prevSize), add - SEGMENT_FOOTER_SIZE, sizeof(int));
	memcpy(&(prev), add - prevSize - SEGMENT_FOOTER_SIZE - SEGMENT_HEADER_SIZE + FREE, sizeof(char));
	memcpy(&(next), add + size + SEGMENT_FOOTER_SIZE + SEGMENT_HEADER_SIZE + FREE, sizeof(char));
	if (next) {
		if (prev) {
			/* both neighbors are free */
			mergeFree(add, size, add - prevSize - SEGMENT_FOOTER_SIZE - SEGMENT_HEADER_SIZE, prevSize, add + size + SEGMENT_FOOTER_SIZE + SEGMENT_HEADER_SIZE);
		}
		else {
			/* only next is free */
			mergeFree(add, size, NULL, 0, add + size + SEGMENT_FOOTER_SIZE + SEGMENT_HEADER_SIZE);
		}
	} 
	else {
		if (prev) {
			/* only prev is free */
			mergeFree(add, size, add - prevSize - SEGMENT_FOOTER_SIZE - SEGMENT_HEADER_SIZE, prevSize, NULL);
		}
		else createFree(add, size);
	}
}

/* frees the whole structure */
void freeAll() {
	void *curr, *next;
	int size;
	memcpy(&(curr), memHead, sizeof(void*)); /* ??? */
	while (curr != NULL) {
		memcpy(&(size), curr + SIZE, sizeof(int));
		memcpy(&(next), curr + NEXT, sizeof(void*)); /* ??? */
		munmap(curr, size);
		curr = next;
	}
}




